﻿/**
 * @file std_rbtree.h
 * Copyright (c) 2019 Gaaagaa. All rights reserved.
 * 
 * @author  : Gaaagaa
 * @date    : 2019-09-09
 * @version : 1.0.0.0
 * @brief   : 使用 C API 的接口形式实现 红黑树 容器。
 */

/**
 * The MIT License (MIT)
 * Copyright (c) Gaaagaa. All rights reserved.
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy of
 * this software and associated documentation files (the "Software"), to deal in
 * the Software without restriction, including without limitation the rights to
 * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is furnished to do
 * so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
 * FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR
 * COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
 * IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#ifndef __STD_RBTREE_H__
#define __STD_RBTREE_H__

#include "std_comm.h"

////////////////////////////////////////////////////////////////////////////////

#ifdef __cplusplus
extern "C"
{
#endif // __cplusplus

////////////////////////////////////////////////////////////////////////////////
// 红黑树的相关数据定义以及操作接口

//====================================================================

// 
// xstd_rbtree_t 的相关数据定义
// 

#define XRBT_FALSE           XSTD_FALSE
#define XRBT_TRUE            XSTD_TRUE
#define XRBT_NULL            XSTD_NULL

typedef xstd_void_t          xrbt_void_t;
typedef xstd_bool_t          xrbt_bool_t;
typedef xstd_size_t          xrbt_size_t;
typedef xstd_elem_t          xrbt_elem_t;
typedef xstd_ctxt_t          xrbt_ctxt_t;
typedef xstd_func_compare_t  xrbt_kcmpfunc_t;

/** 声明 xstd_rbtree_t 对象指针类型 */
typedef struct xstd_rbtree_t * xrbt_this_t;

/** 声明 xstd_rbtree_t 所使用的节点迭代器 */
typedef struct xrbt_node_t * xrbt_iter_t;

//====================================================================

// 
// xstd_rbtree_t 的相关操作接口
// 

/**********************************************************/
/**
 * @brief 返回内部的 sizeof(xstd_rbtree_t) 值。
 */
xrbt_size_t std_rbtree_sizeof(void);

/**********************************************************/
/**
 * @brief 创建 xstd_rbtree_t 对象。
 * @note
 * 1. xfunc_initial 与 xfunc_release 在实现流程中应起到资源 初始化/释放 的对应关系。
 * 2. 请使用 @see std_rbtree_destroy() 销毁返回的对象。
 * 
 * @param [in ] xrbt_ctxt  : 红黑树所存储节点元素值的类型上下文描述信息。
 * @param [in ] xfunc_kcmp : 比较 节点元素 的回调函数（为 XRBT_NULL 时，取内部默认函数）。
 * 
 * @return xrbt_this_t : 
 * xstd_rbtree_t 对象指针；若 返回 XRBT_NULL，则表示创建失败。
 */
xrbt_this_t std_rbtree_create(
                xrbt_ctxt_t xrbt_ctxt,
                xrbt_kcmpfunc_t xfunc_kcmp);

/**********************************************************/
/**
 * @brief 销毁 xstd_rbtree_t 对象，其由 @see std_rbtree_create() 所创建。
 */
xrbt_void_t std_rbtree_destroy(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 在已开辟 xstd_rbtree_t 对象缓存的位置上创建 xstd_rbtree_t 对象。
 * @note
 * 1. xrbt_this 的缓存大小必须大于等于 sizeof(xstd_rbtree_t) 值。
 * 2. xrbt_this 对象销毁时，请使用 @see std_rbtree_emplace_destroy() 。
 * 3. 其他参数请参看 @see std_rbtree_create() 对应的参数说明。
 */
xrbt_this_t std_rbtree_emplace_create(
                xrbt_this_t xrbt_this,
                xrbt_ctxt_t xrbt_ctxt,
                xrbt_kcmpfunc_t xfunc_kcmp);

/**********************************************************/
/**
 * @brief
 * 在已开辟 xstd_rbtree_t 对象缓存的位置上销毁 xstd_rbtree_t 对象，
 * 其由 @see std_rbtree_emplace_create() 所创建。
 */
xrbt_void_t std_rbtree_emplace_destroy(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的 上下文信息。
 */
xrbt_ctxt_t std_rbtree_ctxt(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的类型标识。
 */
xrbt_size_t std_rbtree_etype(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的节点数量。
 */
xrbt_size_t std_rbtree_size(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 判断 xstd_rbtree_t 对象中节点数量是否为空。
 */
xrbt_bool_t std_rbtree_empty(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象可容纳最大节点数量。
 */
xrbt_size_t std_rbtree_maxsize(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的左手臂长度。
 */
xrbt_size_t std_rbtree_left_length(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象中的右手臂长度。
 */
xrbt_size_t std_rbtree_right_length(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 清除 xstd_rbtree_t 对象中的所有节点。
 */
xrbt_void_t std_rbtree_clear(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象插入新节点。
 * 
 * @param [in,out] xrbt_this : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem : 新节点的元素值。
 * 
 * @param [out   ] xbt_clash : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_insert(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_bool_t * xbt_clash);

/**********************************************************/
/**
 * @brief 向 xstd_rbtree_t 对象安放新节点。
 * 
 * @param [in,out] xrbt_this : xstd_rbtree_t 对象。
 * 
 * @param [in    ] xrbt_elem : 
 * 新节点的元素值（使用 右值move 操作进行存储）。
 * 
 * @param [out   ] xbt_clash : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，安放操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，安放操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_emplace(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_bool_t * xbt_clash);

/**********************************************************/
/**
 * @brief 
 * 在给出初始检索的节点位置的情况下，
 * 向 xstd_rbtree_t 对象插入新节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xrbt_elem  : 新节点的元素值。
 * @param [in    ] xiter_hint : 给出初始检索的节点位置。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_insert_hint(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_iter_t xiter_hint,
                    xrbt_bool_t * xbt_clash);

/**********************************************************/
/**
 * @brief 
 * 在给出初始检索的节点位置的情况下，
 * 向 xstd_rbtree_t 对象安放新节点。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * 
 * @param [in    ] xrbt_elem  : 
 * 新节点的元素值（使用 右值move 操作进行存储）。
 * 
 * @param [in    ] xiter_hint : 给出初始检索的节点位置。
 * 
 * @param [out   ] xbt_clash  : 
 * 检测所插入的 新节点元素值 是否与 xstd_rbtree_t 对象中
 * 原有的 节点元素值 是否冲突。
 * 入参不为 XRBT_NULL 时，
 *  若返回值为 XRBT_TRUE，表示产生冲突，插入操作算是失败的；
 *  否则，返回 XRBT_FALSE，表示产生冲突，插入操作
 *  算是（新增节点）成功的。
 * 入参为 XRBT_NULL 时，则忽略该检测操作。
 * 
 * @return xrbt_iter_t : 返回 节点元素 对应的 迭代器。
 */
xrbt_iter_t std_rbtree_emplace_hint(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem,
                    xrbt_iter_t xiter_hint,
                    xrbt_bool_t * xbt_clash);

/**********************************************************/
/**
 * @brief 从 xstd_rbtree_t 对象中删除指定节点。
 */
xrbt_void_t std_rbtree_erase(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 从 xstd_rbtree_t 对象中删除指定元素值的节点。
 * 
 * @return xrbt_bool_t : 操作是否成功。
 * 返回 XRBT_FALSE 时，表示 指定的元素值，
 * 未存储于 xstd_rbtree_t 对象中。
 */
xrbt_bool_t std_rbtree_erase_elem(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem);

/**********************************************************/
/**
 * @brief 将节点对象停靠（插入）到 xstd_rbtree_t 中。
 * @note
 * xiter_node 必须处于分离状态（参看 @see std_rbtree_undocked()），
 * 而且其节点元素类型必须 与 xrbt_this 存储的节点类型相同。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xiter_node : 停靠操作的节点对象。
 * 
 * @return xrbt_iter_t : 节点对象。
 * - 返回的 节点对象 == xiter_node，停靠成功。
 * - 返回的 节点对象 != xiter_node，停靠失败（节点元素值冲突）。
 */
xrbt_iter_t std_rbtree_dock(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 将节点对象从 xstd_rbtree_t 中分离（移除）出来。
 * @note  xiter_node 当前必须隶属于 xrbt_this 。
 * 
 * @param [in,out] xrbt_this  : xstd_rbtree_t 对象。
 * @param [in    ] xiter_node : 分离操作的节点对象。
 * 
 * @return xrbt_iter_t : 返回的 节点对象 == xiter_node。
 */
xrbt_iter_t std_rbtree_undock(xrbt_this_t xrbt_this, xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 将 xrbt_other 对象中的节点转移到 xrbt_this 对象中。
 * @note 
 * 1. xrbt_other 与 xrbt_this 的节点存储类型必须一致。
 * 2. xrbt_other 与 xrbt_this 的节点，可能有相同值的节点，
 *    这部分节点不会被转移，完成操作后，依然会保留在 xrbt_other 中。
 * 
 * @param [in,out] xrbt_this  : 转移至的目标 红黑树对象。
 * @param [in,out] xrbt_other : 被转移的源 红黑树对象。
 */
xrbt_void_t std_rbtree_merge(xrbt_this_t xrbt_this, xrbt_this_t xrbt_other);

/**********************************************************/
/**
 * @brief 在 xstd_rbtree_t 对象中查找指定节点。
 * @note  若返回 NIL 则表示 xstd_rbtree_t 对象不包含该节点元素值。
 */
xrbt_iter_t std_rbtree_find(xrbt_this_t xrbt_this, xrbt_elem_t xrbt_elem);

/**********************************************************/
/**
 * @brief 返回的是首个不小于 指定节点元素值 的 节点位置。
 */
xrbt_iter_t std_rbtree_lower_bound(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem);

/**********************************************************/
/**
 * @brief 返回的是首个大于 指定节点元素值 的 节点位置。
 */
xrbt_iter_t std_rbtree_upper_bound(
                    xrbt_this_t xrbt_this,
                    xrbt_elem_t xrbt_elem);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的根节点。
 */
xrbt_iter_t std_rbtree_root(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的正向遍历操作的起始节点。
 */
xrbt_iter_t std_rbtree_begin(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的正向遍历操作的终止节点。
 */
xrbt_iter_t std_rbtree_end(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回（正向）下一个节点迭代器。
 */
xrbt_iter_t std_rbtree_next(xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的反向遍历操作的起始节点。
 */
xrbt_iter_t std_rbtree_rbegin(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回 xstd_rbtree_t 对象的反向遍历操作的终止节点。
 */
xrbt_iter_t std_rbtree_rend(xrbt_this_t xrbt_this);

/**********************************************************/
/**
 * @brief 返回（反向的）下一个节点迭代器。
 */
xrbt_iter_t std_rbtree_rnext(xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 返回 迭代器 对应存储的节点元素。
 */
xrbt_elem_t std_rbtree_elem(xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 判断 节点对象 是否为 NIL 。
 */
xrbt_bool_t std_rbtree_isnil(xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 判断 节点对象 是否为 非停靠状态（即其已被分离出 xstd_rbtree_t）。
 */
xrbt_bool_t std_rbtree_undocked(xrbt_iter_t xiter_node);

/**********************************************************/
/**
 * @brief 返回 节点对象 所隶属的 xstd_rbtree_t 。
 * @note 
 * 1. xiter_node 迭代器必须处于 停靠状态。
 * 2. 内部会进行节点遍历操作，使用时应注重效率问题。
 */
xrbt_this_t std_rbtree_owner(xrbt_iter_t xiter_node);

////////////////////////////////////////////////////////////////////////////////

/** 
 * @brief 
 * 为 xstd_rbtree_t 的基础数据类型容器，
 * 定义简化版操作接口的宏。
 */
#define XSTD_RBTREE_TYPE_FUNC(xtype, xname)         \
                                                    \
static inline xrbt_this_t                           \
    std_rbtree_create_##xname(void)                 \
{                                                   \
    return std_rbtree_create(                       \
                &xstd_ctxt_##xname,                 \
                xstd_fcmp_##xname.xfunc_lt);        \
}                                                   \
                                                    \
static inline xrbt_iter_t                           \
    std_rbtree_insert_##xname(                      \
        xrbt_this_t xrbt_this,                      \
        xtype xrbt_elem)                            \
{                                                   \
    return std_rbtree_insert(                       \
                xrbt_this,                          \
                &xrbt_elem,                         \
                XRBT_NULL);                         \
}                                                   \
                                                    \
static inline xrbt_iter_t                           \
    std_rbtree_insert_hint_##xname(                 \
        xrbt_this_t xrbt_this,                      \
        xtype xrbt_elem,                            \
        xrbt_iter_t xiter_hint)                     \
{                                                   \
    return std_rbtree_insert_hint(                  \
                xrbt_this,                          \
                &xrbt_elem,                         \
                xiter_hint,                         \
                XRBT_NULL);                         \
}                                                   \
                                                    \
static inline xrbt_bool_t                           \
    std_rbtree_erase_##xname(                       \
        xrbt_this_t xrbt_this,                      \
        xtype xrbt_elem)                            \
{                                                   \
    return std_rbtree_erase_elem(                   \
                xrbt_this,                          \
                &xrbt_elem);                        \
}                                                   \
                                                    \
static inline xtype                                 \
    std_rbtree_##xname(                             \
        xrbt_iter_t xiter_trav)                     \
{                                                   \
    return *(xtype *)std_rbtree_elem(xiter_trav);   \
}

//====================================================================

XSTD_RBTREE_TYPE_FUNC(xstd_char_t   , char   )  // 对应 xstd_char_t    类型
XSTD_RBTREE_TYPE_FUNC(xstd_uchar_t  , uchar  )  // 对应 xstd_uchar_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_int8_t   , int8   )  // 对应 xstd_int8_t    类型
XSTD_RBTREE_TYPE_FUNC(xstd_int16_t  , int16  )  // 对应 xstd_int16_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_int32_t  , int32  )  // 对应 xstd_int32_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_int64_t  , int64  )  // 对应 xstd_int64_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_uint8_t  , uint8  )  // 对应 xstd_uint8_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_uint16_t , uint16 )  // 对应 xstd_uint16_t  类型
XSTD_RBTREE_TYPE_FUNC(xstd_uint32_t , uint32 )  // 对应 xstd_uint32_t  类型
XSTD_RBTREE_TYPE_FUNC(xstd_uint64_t , uint64 )  // 对应 xstd_uint64_t  类型
XSTD_RBTREE_TYPE_FUNC(xstd_long_t   , long   )  // 对应 xstd_long_t    类型
XSTD_RBTREE_TYPE_FUNC(xstd_llong_t  , llong  )  // 对应 xstd_llong_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_ulong_t  , ulong  )  // 对应 xstd_ulong_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_ullong_t , ullong )  // 对应 xstd_ullong_t  类型
XSTD_RBTREE_TYPE_FUNC(xstd_float_t  , float  )  // 对应 xstd_float_t   类型
XSTD_RBTREE_TYPE_FUNC(xstd_double_t , double )  // 对应 xstd_double_t  类型
XSTD_RBTREE_TYPE_FUNC(xstd_ldouble_t, ldouble)  // 对应 xstd_ldouble_t 类型
XSTD_RBTREE_TYPE_FUNC(xstd_handle_t , handle )  // 对应 xstd_handle_t  类型

////////////////////////////////////////////////////////////////////////////////

#ifdef __cplusplus
}; // extern "C"
#endif // __cplusplus

////////////////////////////////////////////////////////////////////////////////

#endif // __STD_RBTREE_H__
